import java.util.*;
import java.lang.Integer;
import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;

public class candy {
    public static int candy(int[] ratings) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        // 0. remove duplication
        // 1. Find local min, and local max
        // 2. Assign the min as 1 then propergate the assignment upto the local max
        // 3. Sum it over all the assigned array element
        
        int len = ratings.length;
        if (len == 0) return 0;
        if (len == 1) return 1;
        if (len == 2) {
            if (ratings[0] != ratings[1]) {
                return 3;
            } else {
                return 2;
            }
        }
        
        // DEBUG
        System.out.println("length is " + len);
        
        HashSet<Integer> local_min_index = new HashSet<Integer>();
        HashSet<Integer> local_max_index = new HashSet<Integer>();
        int[] candies = new int[len];
        
        // initiate the candies as -1
        for (int i = 0; i < len; i++) {
            candies[i] = -1;
        }
        
        // find the local min or max
        for (int i = 1; i < len - 1; i++) {
            if (ratings[i] <= ratings[i+1] && ratings[i] <= ratings[i-1]) {
                local_min_index.add(i);
            }
            if (ratings[i] >= ratings[i+1] && ratings[i] >= ratings[i-1]) {
                // excluding the equivalent case
                if (ratings[i] != ratings[i+1] || ratings[i] != ratings[i-1]) {
                    local_max_index.add(i);
                }
            }
        }
        
        // DEBUG
        System.out.println("Local min before endpoint: " + local_min_index);
        System.out.println("Local max before endpoint: " + local_max_index);
        
        // handle endpoint
        if (ratings[0] <= ratings[1] ) {
            local_min_index.add(0);
        } else {
            local_max_index.add(0);
        }
        
        if (ratings[len - 1] <= ratings[len - 2]) {
            local_min_index.add(len - 1);
        } else {
             local_max_index.add(len - 1);
        }
        
        // DEBUG
        System.out.println("Local min after endpoint: " + local_min_index);
        System.out.println("Local max after endpoint: " + local_max_index);
        
        // assign the ratings start from the local min
        for (int i : local_min_index) {
            // DEBUG
            System.out.println("Current index is " + i);
            candies[i] = 1;
            int left_index = i - 1, left_value = 1, right_index = i + 1, right_value = 1;
            // assign left
            while (left_index >= 0) {
                left_value++;
                if (local_max_index.contains(left_index)) {
                    if (candies[left_index] < left_value) {
                        candies[left_index] = left_value;
                    }
                    break;
                } else if (local_min_index.contains(left_index)) {
                    break;
                } else {
                    candies[left_index] = left_value;
                }
                left_index--;
            }
            // assign right
            while(right_index < len) {
                right_value++;
                if (local_max_index.contains(right_index)) {
                    if (candies[right_index] < right_value) {
                        candies[right_index] = right_value;
                    }
                    break;
                } else if (local_min_index.contains(right_index)) {
                    break;
                } else {
                    candies[right_index] = right_value;
                }
                right_index++;
            }
        }
        
        // DEBUG
        
        
        // sum it up
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += candies[i];
        }
        return sum;
    }
    
    public static void main(String[] args) {
      String FILENAME = "D:\\Snoopy\\Programming\\Interview\\Java\\LeetCode\\Candy\\test.txt";
      Path path = Paths.get(FILENAME);
      try {
        Scanner scanner =  new Scanner(path);
        String nextLine = scanner.next();
        String [] splitedLine = nextLine.substring(1, nextLine.length() - 1).split(",");
        int splitedLen = splitedLine.length;
        int [] numSeq = new int[splitedLen];
        for (int i = 0; i < splitedLen; i++) {
          numSeq[i] = Integer.parseInt(splitedLine[i]);
        }
        System.out.println("Min sum is " + candy(numSeq));
      } catch(IOException e) {
        System.out.println("IO Error: file not exist!!!");
      }
    }
}